/*
 * @lc app=leetcode.cn id=42 lang=java
 *
 * [42] 接雨水
 */

// @lc code=start


class Solution {
    public int trap(int[] height) {
        // 1. 暴力法
        // int n = height.length;
        // int ans = 0;
        // for(int i=0; i<n-1; i++) {
        //     int max_left = 0, max_right = 0;
        //     for(int j=i; j>=0; j--) {
        //         max_left = Math.max(max_left, height[j]);
        //     }
        //     for(int j=i; j<n; j++) {
        //         max_right = Math.max(max_right, height[j]);
        //     }
        //     ans += Math.min(max_left, max_right) - height[i];
        // }
        // return ans;

        // 2. 备忘录
        // if(height == null || height.length == 0) return 0;
        // int n = height.length;
        // int ans = 0;
        // // 使用数组作为备忘录， 存储每个位置的左边最高的柱子高度和右边最高的柱子高度
        // int[] max_left = new int[n];
        // int[] max_right = new int[n];
        // max_left[0] = height[0];
        // max_right[n-1] = height[n-1];

        // for(int i=1; i<n; i++) {
        //     max_left[i] = Math.max(max_left[i-1], height[i]);
        // }
        // for(int i=n-2; i>=0; i--) {
        //     max_right[i] = Math.max(max_right[i+1], height[i]);
        // }

        // for(int i=1; i<n-1; i++) {
        //     ans += Math.min(max_left[i], max_right[i]) - height[i];
        // }
        // return ans;

        // 3. 双指针
        if(height == null || height.length == 0) return 0;
        int n = height.length;
        int left = 0, right = n-1;
        int ans = 0;

        int lmax = height[0], rmax = height[n-1];

        while(left < right) {
            lmax = Math.max(lmax, height[left]);
            rmax = Math.max(rmax, height[right]);

            if(lmax < rmax) {
                ans += lmax - height[left];
                left++;
            } else {
                ans += rmax - height[right];
                right--;
            }
        }
        return ans;
    }
}
// @lc code=end

